package com.zyk.problem;

import java.util.Arrays;

/**
 * 最好的切法, 使得最小值尽量大. 求所有位置的答案
 *
 * @author zhangsan
 * @date 2021/5/16 14:38
 */
public class BestSplitForPosition {

    // O(N^3)次方解
    public static int[] bestSplit1(int[] arr) {
        int N = arr.length;
        int[] ans = new int[N];
//        ans[0] = 0;
//        ans[N-1] = 0;
        // 以i结束最优分割尝试
        for (int i = 1; i < N - 1; i++) {   // 控制数组范围: 0~i

            for (int j = 0; j <= i; j++) {   // 每个地方开始尝试, 0 ~ i范围内进行尝试
                int left = 0, right = 0;
                for (int k = 0; k <= j; k++) {
                    left += arr[k];
                }
                for (int k = j + 1; k <= i; k++) {
                    right += arr[k];
                }
                ans[i] = Math.max(ans[i], Math.min(left, right));   // 每种尝试都收集一次答案
            }
        }
        return ans;
    }

    // 2: 使用前置和, 单次O(N) * 求N个位置 = O(N^2).
    public static int[] bestSplit2(int[] arr) {
        int N = arr.length;
        int[] ans = new int[N];
        for (int i = 1; i < N - 1; i++) {   // 控制数组范围: 0~i
            ans[i] = process(arr, 0, i);
        }
        return ans;
    }

    public static int process(int[] arr, int L, int R) {
        int sumAll = 0;
        for (int i = L; i <= R; i++) {
            sumAll += arr[i];
        }
        int ans = 0, sumL = 0;
        for (int i = L; i <= R - 1; i++) {
            sumL += arr[i];
            int sumR = sumAll - sumL;
            ans = Math.max(ans, Math.min(sumL, sumR));
        }
        return ans;
    }


    // 3: 因为非负数组不会回退, 所以在方法2上做优化. O(N)
    public static int[] bestSplit3(int[] arr) {
        int N = arr.length;
        int[] ans = new int[N];
        int[] sum = new int[N];
        sum[0] = arr[0];
        for (int i = 1; i < N; i++) {
            sum[i] = sum[i - 1] + arr[i];
        }

        int preBest = 0;
        int sumL = arr[0], sumR = 0;
        for (int i = 1; i < N - 1; i++) {
            sumR = sum[i] - sumL;   // 新的sumR
            if (sumR > sumL) {
                // L, 往后扩. 上一次划分的位置?
                while (preBest + 1 < i) {   // 别超越范围做事情
                    int before = Math.min(sum(sum, 0, preBest), sum(sum, preBest + 1, i));  // 之前划分不变的这次结果
                    int want = Math.min(sum(sum, 0, preBest + 1), sum(sum, preBest + 2, i));
                    if (want >= before) {
                        preBest++;
                        sumL += arr[preBest];
                        sumR -= arr[preBest];
                    } else {
                        break;
                    }
                }
            }
            ans[i] = Math.min(sumL, sumR);
        }
        return ans;
    }

    // 小公式: 计算sum累加和中, l~r的累加和
    private static int sum(int[] sum, int l, int r) {
        return l == 0 ? sum[r] : sum[r] - sum[l - 1];
    }


    public static void main(String[] args) {
        int[] arr = {3, 11, 7, 17, 15, 1, 17};
        System.out.println(Arrays.toString(bestSplit1(arr)));
        System.out.println(Arrays.toString(bestSplit2(arr)));
        System.out.println(Arrays.toString(bestSplit3(arr)));


        /*int maxLen = 10, maxVal = 20;
        boolean hasMinus = false, fixedSize = false;
        int[] arr = ArrayUtil.generateRandomArray(maxLen, maxVal, hasMinus, fixedSize);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(bestSplit1(arr)));
        System.out.println(Arrays.toString(bestSplit2(arr)));
        System.out.println(Arrays.toString(bestSplit3(arr)));*/

    }



}
